home *** CD-ROM | disk | FTP | other *** search
/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / macros / plain / contrib / treetex / classes.tex < prev    next >
Encoding:
Text File  |  1989-11-22  |  8.2 KB  |  106 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  2. %%% Complete binary trees                                                  %%%  
  3. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  4.                                                                                 
  5. % The macro \b@nary{<number>} expands to the description of a complete          
  6. % binary tree with <number> many internal nodes, where each level is filled with
  7. % the maximal number of internal nodes, and the last level of internal nodes    
  8. % is filled from left to right.                                                 
  9.                                                                                 
  10. \newcount\b@nno % number of nodes                                               
  11. \newcount\b@nlv % number of complete levels                                     
  12. \newcount\b@ndl % number of nodes on incomplete level                           
  13.                                                                                 
  14. \def\ld(#1,#2,#3){% #1, #2, and #3 must be counter registers.                   
  15.                   % #1 is the input, #1 must be >= 1.                           
  16.                   % \ld makes the following assignments:                        
  17.                   % #2:=|_log_2(#1)_|, #3:=2^#2.                                
  18.                   % The contents of #1 is destroyed during the computation.     
  19.      #2=0 #3=1                                                                  
  20.        \loop\ifnum #1>\@ne\relax                                                
  21.             \divide #1 by\tw@ % this is integer division                        
  22.             \advance #2 by\@ne                                                  
  23.             \multiply #3 by\tw@                                                 
  24.      \repeat}                                                                   
  25.                                                                                 
  26. \def\b@nary#1{% draws a complete binary tree with #1 internal nodes,            
  27.            % a complete binary tree with N internal nodes has                   
  28.            % lv:=|_log_2(N+1)_| many                                            
  29.            % complete level of binary nodes and dl:=N-2^{lv}+1 many internal    
  30.            % nodes on an incomplete level.                                      
  31.      \b@nno=#1\relax\advance\b@nno by \@ne                                      
  32.      \ld(\b@nno,\b@nlv,\b@ndl)%                                                 
  33.      \b@ndl=-\b@ndl\advance\b@ndl by #1\advance\b@ndl by\@ne                    
  34.      \b@n}                                                                      
  35.                                                                                 
  36. \def\b@n{%                                                                      
  37.      \ifnum\b@nlv>\@ne                                                          
  38.            \advance\b@nlv by-\@ne                                               
  39.            \b@n                                                                 
  40.            \b@n                                                                 
  41.            \advance\b@nlv by\@ne                                                
  42.            \node{}                                                              
  43.       \else\ifnum\b@ndl>\@ne                                                    
  44.                  \advance\b@ndl by-\tw@                                         
  45.                  \node{\le@f\external}\node{\le@f\external}\node{}%             
  46.                  \node{\le@f\external}\node{\le@f\external}\node{}%             
  47.                  \node{}%                                                       
  48.             \else\ifnum\b@ndl=\@ne                                              
  49.                        \advance\b@ndl by-\@ne                                   
  50.                        \node{\le@f\external}\node{\le@f\external}\node{}%       
  51.                        \node{\le@f\external}%                                   
  52.                        \node{}%                                                 
  53.                   \else\node{\le@f\external}\node{\le@f\external}\node{}%       
  54.                     \fi                                                         
  55.               \fi                                                               
  56.         \fi}                                                                    
  57.                                                                                 
  58. \def\circleleaves{\def\le@f{\type{circle}}}                                     
  59. \def\squareleaves{\def\le@f{\type{square}}}                                     
  60.                                                                                 
  61. \newcount\no@                                                                   
  62. \def\no#1{\no@=#1\relax}                                                        
  63.                                                                                 
  64. \def\binary#1{%                                                                 
  65.      \no{1}\circleleaves                                                        
  66.      #1%                                                                        
  67.      \b@nary{\no@}}                                                             
  68.                                                                                 
  69. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  70. %%% Fibonacci trees                                                        %%%  
  71. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  72.                                                                                 
  73. % \f@b expands to the description of a Fibonacci tree                           
  74. % of height \f@bht.                                                             
  75.                                                                                 
  76. \newcount\f@bht                                                                 
  77.                                                                                 
  78. \def\f@b{% draws a Fibonacci tree of depth #1                                   
  79.      \ifnum\f@bht>1                                                             
  80.            \advance\f@bht by-\@ne\f@b\advance\f@bht by\@ne                      
  81.            \advance\f@bht by-\tw@\f@b\advance\f@bht by\tw@                      
  82.            \ifunn@des\node{\unary}                                              
  83.                   \fi                                                           
  84.            \node{\lefttop}                                                      
  85.       \else\ifnum\f@bht=1                                                       
  86.                  \node{\external\le@f}                                          
  87.                  \node{\external\le@f}                                          
  88.                  \node{}                                                        
  89.             \else\node{\external\le@f}                                          
  90.               \fi                                                               
  91.         \fi}                                                                    
  92.                                                                                 
  93. \newif\ifunn@des                                                                
  94.                                                                                 
  95. \let\unarynodes\unn@destrue                                                     
  96. \def\hght#1{\f@bht=#1\relax}                                                    
  97.                                                                                 
  98. \def\fibonacci#1{%                                                              
  99.      \hght{0}\unn@desfalse\circleleaves                                         
  100.      #1%                                                                        
  101.      \f@b}                                                                      
  102.                                                                                 
  103.                                                                                 
  104. %                                                                               
  105.  
  106.